//给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。 
//
// 例如，如果 arr = [1, 2] ，
// k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。 
//
// 返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。 
//
// 由于 结果可能会很大，需要返回的
// 10⁹ + 7 的 模 。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [1,2], k = 3
//输出：9
// 
//
// 示例 2： 
//
// 
//输入：arr = [1,-2,1], k = 5
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：arr = [-1,-2], k = 7
//输出：0
// 
//
// 
//
// 提示： 
// 
//
// 
// 1 <= arr.length <= 10⁵ 
// 1 <= k <= 10⁵ 
// -10⁴ <= arr[i] <= 10⁴ 
// 
//
// Related Topics 数组 动态规划 👍 146 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//java:K 次串联后最大子数组之和
public class Q1191KConcatenationMaximumSum {
    public static void main(String[] args){
        Solution solution = new Q1191KConcatenationMaximumSum().new Solution();
        solution.kConcatenationMaxSum(new int[]{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}, 100000);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        int n = arr.length, MOD = 1_000_000_007;
        int[] dp = new int[n * k];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[0] = arr[0];
                } else {
                    dp[i * n + j] = Math.max(dp[i * n + j - 1] + arr[j], arr[j]) % MOD;
                }
            }
        }
        return Math.max(Arrays.stream(dp).max().getAsInt(), 0);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}